/*
 * @lc app=leetcode.cn id=90 lang=javascript
 *
 * [90] 子集 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var subsetsWithDup = function(nums) {
  nums.sort((a, b) => a - b)
  const res = []
  let used = []

  const dfs = (start, list) => {
    res.push(list.slice())
    for (let i = start; i < nums.length; i++) {
      // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
      // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
      if (i > 0 && nums[i] == nums[i-1] && [undefined, false].includes(used[i-1])) continue
      list.push(nums[i])
      used[i] = true
      dfs(i + 1, list)
      used[i] = false
      list.pop()
    }
  }
  
  dfs(0, [])
  return res
};
// @lc code=end

// var subsetsWithDup = function(nums) {
//   nums.sort((a, b) => a - b)
//   const res = []

//   const dfs = (choosePre, index, list) => {
//     if (index === nums.length) {
//       return res.push(list.slice())
//     }
//     dfs(false, index+1, list)
//     if (!choosePre && index > 0 && nums[index - 1] === nums[index]) return
//     // 选
//     list.push(nums[index])
//     dfs(true, index+1, list)
//     // 跳过当前选项
//     list.pop()
//   }
  
//   dfs(false, 0, [])
//   return res
// };